package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 1987. 不同的好子序列数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/12 9:45
 */
public class NumberOfUniqueGoodSubsequences {

    public static void main(String[] args) {
        NumberOfUniqueGoodSubsequences test = new NumberOfUniqueGoodSubsequences();

        // 2
//        String binary = "001";

        // 2
//        String binary = "11";

        // 5
//        String binary = "101";

        // 5
        String binary = Utils.getStr(100000, '0', '1');

        int i = test.numberOfUniqueGoodSubsequences(binary);
        System.out.println(i);

    }

    public int numberOfUniqueGoodSubsequences(String binary) {
        long oneCount = 0;
        long one0 = 0;
        long one1 = 0;
        long zeroCount = 0;
        long zero0 = 0;
        long zero1 = 0;
        boolean flag = false;
        long all = 0;
        long t = 1000000007;
        for (char c : binary.toCharArray()) {
            if (c == '0') {
                flag = true;
                if (oneCount == 0) {
                    continue;
                }
                long c0 = zeroCount - zero0;
                if (c0 < 0) {
                    c0 += t;
                }
                all += c0;
                long c1 = oneCount - one0;
                if (c1 < 0) {
                    c1 += t;
                }
                all += c1;
                zero0 = zeroCount;
                zeroCount = (zeroCount + c0) % t;
                one0 = oneCount;
                oneCount = (oneCount + c1) % t;
            } else {
                if (oneCount == 0) {
                    oneCount = 1;
                    all += 1;
                    continue;
                }
                long c0 = zeroCount - zero1;
                if (c0 < 0) {
                    c0 += t;
                }
                all += c0;
                long c1 = oneCount - one1;
                if (c1 < 0) {
                    c1 += t;
                }
                all += c1;
                zero1 = zeroCount;
                zeroCount = (zeroCount + c0) % t;
                one1 = oneCount;
                oneCount = (oneCount + c1) % t;
            }
           all =  all % 1000000007;
        }
        return (int) (flag ? all + 1 : all);
    }

}
